//
// Created by shenbin on 2022/5/8.
// https://leetcode-cn.com/problems/powx-n/submissions/
//

#ifndef ALGORITHM_TRAINNING_C04_LC50_H
#define ALGORITHM_TRAINNING_C04_LC50_H

/**
 * 分治：
 * 1. n 为 奇数：
 * 2. n 为 偶数:
 * 3. n 为 0：return 1；
 * 4. n 为 int的下界： return 1.0 / (myPow(x, -(n + 1)) * x);
 */
class LeetCode50 {
public:
    double myPow(double x, int n) {
        if (n == 0) return 1;
        if (n == -(1ll << 31)) return 1.0 / (myPow(x, -(n + 1)) * x);
        if (n < 0) return 1.0 / myPow(x, -n);
        double temp = myPow(x, n / 2);
        double ans = temp * temp;
        if (n % 2 == 1) ans *= x;
        return ans;

    }
};

#endif //ALGORITHM_TRAINNING_C04_LC50_H
